home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _dfsnum.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.5 KB  |  60 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _dfsnum.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  DFS_NUM (depth first search numbering)                                      *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. static int dfs_count1,dfs_count2;
  27.  
  28. static void dfs(node v, node_array<bool>& reached, 
  29.                         node_array<int>& dfsnum, 
  30.                         node_array<int>& compnum,
  31.                         list<edge>& T )
  32. { node w;
  33.   edge e;
  34.  
  35.   reached[v] = true;
  36.   dfsnum[v] = ++dfs_count1;
  37.  
  38.   forall_adj_edges(e,v) 
  39.     { w = target(e);
  40.       if (!reached[w]) 
  41.        { T.append(e);
  42.          dfs(w,reached,dfsnum,compnum,T);
  43.         }
  44.      }
  45.  
  46.   compnum[v] = ++dfs_count2;
  47. } 
  48.  
  49. list<edge> DFS_NUM(const graph& G, node_array<int>& dfsnum, 
  50.                                    node_array<int>& compnum)
  51. { 
  52.   list<edge> T;
  53.   node_array<bool> reached(G,false);
  54.   node v;
  55.   dfs_count1 = dfs_count2 = 0;
  56.   forall_nodes(v,G) if (!reached[v]) dfs(v,reached,dfsnum,compnum,T);
  57.   return T;
  58. }
  59.  
  60.